1. Field of the Invention
The present invention relates to a reconfigurable device in which various functions can be implemented by a user, and in particular to a function block which is a logic function constituting unit. More specifically, the present invention relates to a function block suitable for implementing a multiplier and a multiplexer. In this specification, a circuit bearing a main portion of a logic function in a programmable function cell is referred to as a function block.
2. Description of the Related Art
Recently, reconfigurable devices such as a PLD (programmable logic device), FPGA (field programmable gate array) and the like in which various functions can be set by a user have been rapidly developed. With increase of degree of integration and speed, such a reconfigurable device is expected to be used not only for emulation during the designing of ASIC (application-specific integrated circuit) or substitution of a simple peripheral circuit but also for a reconfigurable computer whose hardware structure can be changed depending on an application.
However, a multiplier that is frequently used in computing cannot be effectively realized by a conventional PLD or FPGA, which is one of the causes disturbing practical use of a reconfigurable computer. Furthermore, the conventional PLD and FPGA cannot effectively realize a multi-input multiplexer (MUX). Owing to this, it has been impossible to obtain a compact barrel shifter, for example, used for floating-point addition/subtraction.
FIG. 103 shows a typical example of an ordinary multiplier. This multiplier multiplies
X=x7x6x5x4x3x2x1x0 by Y=y3y2y1y0 to produce
Z=z11z10z9z8z7z6z5z4z3z2z1z0 that is the product of X and Y, where each of xi, yi or zi represents (i+1)-th bit of binary data X, Y and Z, and is 0 or 1 (i=0, 1, 2, . . . ). For example, the notation of x7x6x5x4x3x2x1x0 represents a bit arrangement of binary data X. As is clear from FIG. 103, this multiplier is constructed by systematically arranging a multiplier unit 76 in an array. In the multiplier unit 76, an output of an AND circuit 31 is connected to one argument input b of a 1-bit full adder 43. In the 1-bit full adder 43 of FIG. 103, the other argument input is denoted by a, a carry input by ic, a carry output by oc, and an addition output by s. The multiplier as shown in FIG. 103 is the most basic array-type multiplier having a simple and systematic configuration, which is suitable for implementation in the FPGA.
FIG. 104 shows an example of a conventional function block 4 for FPGA (for example, see U.S. Pat. Nos. 5,349,250, 5,481,206, and 5,546,018). Here, only those parts related to the description are shown. In the figure, a logic function generator 40 is a circuit capable of realizing various logic functions in accordance with contents of a built-in configuration memory.
FIG. 105 shows an example of the logic function generator 40. This has sixteen 1-bit memory cells 13 as a configuration memory and the outputs of respective ones of the memory cells are inputted to a 16-input multiplexer (MUX) 20. In accordance with values of four control inputs in0, in1, in2 and in3, the 16-input MUX 20 selects one of the 16 inputs to output it as denoted by out. This logic function generator 40 has a logic function which is determined in accordance with contents stored in the configuration memory 13 and can realize an arbitrary 4-input 1-output logic function having four inputs in0, in1, in2 and in3 and one output. In general, a logic function generator having 2k-bit memory cells and capable of realizing all the k-input 1-output logic functions is referred to as a Look-Up Table (hereinafter, abbreviated as LUT). FIG. 105 shows an example of 4-input LUT. Examples of other configurations of the LUT are disclosed in, for example, U.S. Pat. Re. 34,363 and U.S. Pat. No. 4,706,216.
The function block 4 of FIG. 104 uses the logic function generator 40 to which a 2-input MUX 22 as a ripple carry circuit and a 2-input exclusive OR circuit (XOR) 30 required for constituting an adder are added.
With regard to the 2-input MUX, see FIG. 7. In FIG. 7, the 2-input MUX 22 has an input to which input in0 is connected (input-0) and another input to which input in1 is connected (input-1). When a control input in2 is logical 0, a signal in0 fed to the input-0 is outputted as denoted by out, and when the control input in2 is logical 1, a signal in1 fed to the input-1 is outputted. Hereinafter, when MUX is briefly written as “MUX” omitting the number of inputs, it represents two inputs (exclusive of a control input).
The multiplier of FIG. 103 may be configured using the function block 4 of FIG. 104 to implement the function as shown in FIG. 106 in the logic function generator 40 of FIG. 104. In this case, the function block 4 of FIG. 104 functions as the multiplier unit 76 of FIG. 103. Here, an input in0, an output os, a ripple carry input irc, and a ripple carry output orc of FIG. 104 correspond to the argument input a, the adder output s, the carry input ic, and the carry output oc of the 1-bit full adder 43, respectively. Moreover, the AND 31 in the circuit of FIG. 106 implemented in the logic function generator 40 of FIG. 104 corresponds to the AND 31 in the multiplier unit 76 of FIG. 103.
As has been described above, the multiplier unit 76 of FIG. 103 can be constructed of one function block 4 of FIG. 104. However, when a multiplier is constructed by this method, multiplication of m-bit data and n-bit data requires m×n function blocks, occupying a great area. Furthermore, in the case of a multiplier of n bits, a signal should be transferred through n stages of function blocks 4 (besides a carry propagation delay) and accordingly, a signal propagation delay is also increased.
In addition to the function block shown in FIG. 104, several methods have been devised for realizing by a single function block a multiplier unit in which an AND gate is attached to one argument input of a 1-bit full adder (for example, see Japanese Patent Application Laid-open Publication Nos. 11-24891, 11-122096, and 11-353152, and U.S. Pat. No. 5,570,039). These conventional techniques also have the aforementioned problem.
In order to solve the aforementioned problem, U.S. Pat. No. 5,754,459 discloses a method for implementing a multiplier using the modified Booth algorithm and the Wallace Tree into a PLD. However, this multiplier has disadvantages that its circuit configuration is complicated, a plenty of wiring resources is needed, and the area reduction effect is small.
Furthermore, the conventional FPGA has a problem that multi-input (3-input or more in this specification) MUX cannot be effectively realized. As shown in FIG. 104, in the function block 4 having one 4-input logic function generator 40, only one 2-input MUX which is the simplest can be implemented. This is because a 2-input MUX can be realized by three input terminals including a control input while a 3-input MUX requires 5 input terminals and a 4-input MUX requires 6 input terminals. Thus, the 4-input logic function generator cannot provide a sufficient number of inputs.
From this reason, for example, for realizing a 4-input MUX having a high usability by the conventional FPGA, as shown in FIG. 107, it is necessary to use two function blocks 4a and 4b and a MUX 22. (FIG. 107 shows only a portion of the function block related to the present explanation). Here, the logic function generator 40 of each function block has a 2-input MUX (for example, as shown in FIG. 7) implemented therein. In this case, in FIG. 107, two pairs of inputs i0 and i1 of the function blocks 4a and 4b correspond to the four inputs of the 4-input MUX, respectively. The respective inputs i2 and i4 correspond to first and second control inputs of the 4-input MUX. An output om corresponds to the output of the 4-input MUX.
Thus, in order to realize a 4-input MUX by using the conventional FPGA, it is necessary to use two function blocks, resulting in an increase in occupied area. Japanese Patent Laid-open Publication No. 11-24891, Japanese Patent Laid-open Publication Nos. 11-122096 and 11-353152 disclose a completely different type of function block not using the 4-input LUT. However, even with this function block, it is impossible to realize a 4-input MUX in one block.
The floating-point addition/subtraction is performed by using a barrel shifter, which is composed of a large number of MUX'es. When implementing it in the FPGA, such a scheme that a single function block corresponds to one 2-input MUX is inefficient, resulting in increased area. It is desired to realize a 4-input MUX with one function block, thereby greatly improving the efficiency.
A first problem is that when a multiplier is configured by using a conventional function block, the multiplier area and signal propagation delay are increased. When a multiplier unit consisting of a 1-bit full adder and an AND gate is made by one function block, it is necessary to use great many function blocks to complete the entire multiplier.
A second problem is that when constructing a multi-input multiplexer using a conventional function block, the area is increased. Since only one 2-input MUX can be implemented in one function block, plural function blocks should be used to constitute a multi-input MUX.